#include <bits/stdc++.h>
using namespace std;
void build(vector<int>&a,int root,int length)
{
    int left = root<<1|1;
    int right = left+1;
    int max_index = right;
    if(max_index<length)
    {
        if(a.at(max_index)<a.at(left))
            max_index = left;
        if(a.at(max_index)>a.at(root))
        {
            swap(a.at(max_index),a.at(root));
            build(a,max_index,length);
        }

    }
}
void heap_sort(vector<int>&a,int length)
{
    for(int i=length<<1;i>=0;i--)
        build(a,i,length);
    for(int i = a.size()-1;i>0;i--)
    {
        swap(a.at(0),a.at(i));
        build(a,0,i);
    }
}
int main() {
    vector<int> a = {5,23,16,68,94,72,71,84,76};
    int n = a.size();
    heap_sort(a,n);
    for(auto i:a)
        cout<<i<<" ";
    cout<<"\n";
    return 0;
}